This invention relates generally to facsimile pictorial communication systems and more specifically to data compression apparatus.
1. Field of the Invention
It has previously been proposed that documents, for example maps, could be digitized and the resulting data stored electronically in a computer. The stored data could then be recalled from storage, reconstituted and displayed on a display screen or printed on a printer/plotter. If a map, for example, needed correction or updating, the map could be displayed on a screen with which an operator can interact to make any necessary additions or corrections to the displayed map, using, for example a light pen, a keyboard or a tablet apparatus. The updated map can then be restored and/or printed.
An original document which is to be digitized can be scanned by a scanner whose output is a stream of bits which represent picture elements (pels) in successive lines of a raster scan. High resolution scanning requires a resolution of about 120 pels per inch (50 pels per cm) or more: In other words, each one inch of a raster scan line on the document requires 120 pels or more for high resolution. Thus, a document which measures approximately 8.times.12 inches would require about 1.5 million pels to represent that document. It will be appreciated, therefore, that unless provision for compressing the rastered data is made, the requirements for electronic storage of documents could become prohibitive since each pel would require 1 bit of storage.
2. Description of the Prior Art
Various compression techniques have been proposed.
For example, ARPS, U.S. Pat. No. 3,813,485, issued May 28, 1974, "System for Compression of Digital Data", describes the technique for thinning or whitening a black/white image array by way of predictive encoding. In this regard, the predictor estimates what the color value (black or white) should be based upon the color value of contiguous neighborhood pels. If the predicted and actual color values differ then an error value (black pel or `1`) in a counterpart array position is registered. This array of error signals is substantially "whiter than" the original array. Error signals are then run length encoded. The effect of whitening is to reduce the coding to runs of white between errors rather than requiring the encoding of runs of length of both black and white.
T. Morrin, U.S. Pat. No. 3,987,412, issued Oct. 19, 1976, "Image Data Compression Utilizing Boundary Following of the Exterior and Interior Borders of Objects" describes an alternative technique in which a document is scanned in a raster fashion until an object (for example a character) is located. The scan then follows the contour of that object, recording each pel and removing pels from the boundary until the center of the object is reached. The raster scan is then resumed until the next object is encountered. This technique has the advantage that each item of compressed data relates to a single object and therefore each object can be electronically manipulated, for example rotated, while in compressed form.
The present invention is concerned with a different technique which is particularly useful for documents containing graphical information, for example maps.